UVa/10000 - Longest Paths/10000.3.cpp

   1 /*
   2   Accepted
   3  */
   4 #include <queue>
   5 #include <iostream>
   6 #include <vector>
   7
   8 using namespace std;
   9
  10 int main(){
  11   int n;
  12   int C = 1;
  13   while (cin >> n && n){
  14     int start;
  15     cin >> start, --start;
  16
  17     vector<int> g[n];
  18     int p, q;
  19     while (cin >> p >> q && (p+q)){
  20       --p, --q;
  21       g[p].push_back(q);
  22     }
  23     for (int i=0; i<n; ++i){
  24       sort(g[i].begin(), g[i].end());
  25     }
  26
  27     int answer = -1, length = -1;
  28     queue<int> Q;
  29
  30     int d[n];
  31     for (int i=0; i<n; ++i) d[i] = INT_MIN;
  32     Q.push(start);
  33     d[start] = 0;
  34     while (Q.size()){
  35       int u = Q.front();
  36       Q.pop();
  37
  38       if (d[u] > length || (d[u] == length && u < answer)){
  39         answer = u;
  40         length = d[u];
  41       }
  42       vector<int> &vecinos = g[u];
  43       for (int i=0; i<vecinos.size(); ++i){
  44         int v = vecinos[i];
  45         if (d[u] + 1 > d[v]){ //Puedo llegar en un camino más largo
  46           d[v] = d[u] + 1;
  47           Q.push(v);
  48         }
  49       }
  50     }
  51     cout << "Case " << C++ << ": The longest path from " << start + 1 << " has length ";
  52     cout  << length << ", finishing at " << answer + 1 << "." << endl << endl;
  53   }
  54   return 0;
  55 }